PI Calculator version 1.0 ========================= I was cleaning out the piles of paper lying everywhere the other day when I came across some work I did when I was a Uni student. It's been a while since I last worked on this but I thought it would be interesting to see how my new computer did at calculating PI compared to the VAX we used way back in 1986. At the time it was an interesting exercise in writing code in C. Now ten years on I find I'm back to writing code in Pascal. When I originally wrote the programs there were many problems that had to be overcome. The university computer was running Unix and, while originally designed for up to 30 users, could have almost 200 running on it at a time. Response times were hopeless of course. Consequently I used batch jobs to do the processing. Batch processes where limited to 4 hours before they were terminated. However I discovered that while running my calculations the system was so busy that the batch timer didn't kick in until 4 hours 30 minutes. Hence as I increased performance I would have to guess how many digits I would be able to get in a run. After a while I set it up so that there was a series of batch jobs, each one calling the next in series in order to get the three arctan's and then one more to do the final summation. Using this method I was able to calculate 36,000 digits in a run that took about 11 hours to run. Anyway, hope you find this of as much interest as I did. If you use or modify the code remember you need to give me credit for it. Other than that it's all yours. Enjoy. Jason Andre The Formula =========== This information comes from two books. My notes are a bit scratchy and faded now, but, at a guess, 1) The One Million Digits of PI, Guilloud and Bouyer, 1960's? 2) The Computer Age? {I'll check this out one day, or if someone could send me the info then great.} The value of PI was first calculated in 1949 on the ENIAC computer using the formula, pi = 16 arctan(1/5) - 4 arctan(1/239) which is known as machin's Formula. It calculated 2037 digits in 70 hours. The formula I used was, pi = 48 arctan(1/18) + 32 arctan(1/57) - 20 arctan(1/239) this was used on a 7600 Control Data computer to generate 1,000,000 digits in 23 hours and 18 minutes in 196? (I'd assume 1968 or 1969). I presume that calculating the two arctan's, 1/18 and 1/57, is preferred as the partial sums will reduce much quicker than for the arctan 1/5. The Method for calculating the ArcTan ===================================== The arctan is calculated as a series of continuously reducing partial sums, ArcTan 1/K = SUM(p = 0 to infinity) of (-1)^p/(2p + 1)K^(2p+1) The partial sums can be expressed as, Vn+1 = -(2n + 1)/(2n + 3) * 1/K^2 * Vn I use the variables vm for Vn and vn for Vn+1, confusing huh! Still the algorithm is quite simple. The first value of course is for p=0 and this reduces to v0 = 1/K which is what I set both vm and vn to at the start. Then I keep reducing vn and adding or subtracting it from vm which is the current sum. Obvious improvements that can be made to the algorithm ====================================================== 1) The most obvious one, and I will get around to it one day, is to change the array's Vn and Vm, into arrays of integers. Then each array element can store more digits which will immediately improve the performance of the calculation. The change which I have made, from storing single digits, 0..9, in the array, to storing 2 digits, 0..99, pretty well doubled the performance of the algorithm. A similar improvement could be made by switching to an integer with 4 digits, 0..9999. The only thing to watch here is that none of the multiplcations or divides could result in numbers greater than MaxInt. 2) Another thing that might be worth considering once the array has been converted to integers would be to allow up to 8 digits per element but do all calulations with 64 bit integers. I believe 386's and up do support this, they use the eax and edx registers, but I don't think Delphi does. The question of course would be whether or not the extra work handling 64 bit integers would gain you much speed, I assume it would. 3) And of course, the most obvious change, try out Delphi's speed optimizations, I haven't gotten around to looking at these. The Results =========== Arctan Vax 11/780(?) PC 7600 CDC Digits 36,000 50,000 1,000,000 1/18 4h20m 9m33s 9h53m 1/57 3h20m 6m49s 7h04m 1/239 2h20m 5m03s 5h14m PI 1h 1h07m Total ~ 11h 21m25s 23h18m The ZIP supplied with this includes the partial sums and PI for 5000 digits. This took about 13 seconds on my PC. My PC ===== P166 w 32MB DRAM Matrox Millenium 2Mb WRAM 512KB Synchronous SRAM Running Windows 95 I assume that once you go beyond about 100,000 digits the data arrays would not remain cached and so the processing would slow down. (Although once the partial sum reduces it will all run in the cache again). Self Promotion ============== B.Sc. and B.E. (Elec) from Sydney University 9 years programming experience, 7 of them as a Contract Programmer Languages: Assembler (rusty) C, C++ Pascal Major Projects worked on in the past: Delphi Framework, used to hide complexities of a lower level interface (now) Point of Sale system (now) Various Terminal Emulations and Transports (1994-now) Imaging System, Device Level stuff and Image manipulation (1991-1993) Multi-User DOS Kernel (1990) 386 BIOS, Keyboard with a Mouse attached, Device Drivers etc (1989) TSR Messaging System for use on Novell Networks (1987, 1988)